package com.hy.backtracking;

import javax.lang.model.element.VariableElement;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class BackTracking {


    /**
     * 1
     *
     *
     * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
     *
     * 示例:
     * 输入: n = 4, k = 2
     * 输出:
     * [
     * [2,4],
     * [3,4],
     * [2,3],
     * [1,2],
     * [1,3],
     * [1,4],
     * ]
     * 思路
     * 本题这是回溯法的经典题目。
     *
     * 直接的解法当然是使用for循环，例如示例中k为2，很容易想到 用两个for循环，这样就可以输出 和示例中一样的结果。
     * 如果n为100，k为50呢，那就50层for循环，是不是开始窒息。
     * 此时就会发现虽然想暴力搜索，但是用for循环嵌套连暴力都写不出来！
     * 回溯搜索法来了，虽然回溯法也是暴力，但至少能写出来，不像for循环嵌套k层让人绝望。
     *
     * 上面我们说了要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环，那么回溯法就用递归来解决嵌套层数的问题。
     *
     * 递归来做层叠嵌套（可以理解是开k层for循环），每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。
     */
    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combine(int n,int k){
        combineHelper(n,k,1);
        return res;
    }

    /**
     * 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex
     * @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。
     */
    public void combineHelper(int n,int k,int startIndex){
        if (path.size() == k){
            res.add(new ArrayList<>(path));
            return;
        }
        // n - (k - path.size()) 控制组合个数 4-2-0+1
        int x = n - (k - path.size()) + 1;
        for (int i = startIndex; i <= x; i++) {
            path.add(i);
            combineHelper(n,k,i+1);
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        BackTracking backTracking = new BackTracking();

        System.out.println(backTracking.combine(9,3));
    }
}
